1026. 节点与其祖先之间的最大差值【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS

1. 📝 题目描述

• leetcode

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

---

示例 1：

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释：
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

示例 2：

输入：root = [1,null,2,null,0,3]
输出：3

---

提示：

• 树中的节点数在 2 到 5000 之间。
• 0 <= Node.val <= 10^5

2. 🎯 s.1 - DFS

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxAncestorDiff = function (root) {
  let res = 0
  const dfs = (node, minVal, maxVal) => {
    if (!node) return
    res = Math.max(
      res,
      Math.abs(node.val - minVal),
      Math.abs(node.val - maxVal),
    )
    const newMin = Math.min(minVal, node.val)
    const newMax = Math.max(maxVal, node.val)
    dfs(node.left, newMin, newMax)
    dfs(node.right, newMin, newMax)
  }
  dfs(root, root.val, root.val)
  return res
}

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数
• 空间复杂度：$O(n)$，递归调用栈的深度

算法思路：

• DFS 遍历二叉树，沿路径维护祖先节点的最小值 minVal 和最大值 maxVal
• 对于每个节点，计算它与祖先最小值和最大值的差值，更新答案
• 然后更新 minVal 和 maxVal 继续向下递归